/*
题目: 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
 */
public class Offer07 {
    // 先在前序中找一个节点, 根据这个节点在 中序 中找到目标节点
    int inPos = 0; // 中序 数组指针
    int n = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        n = preorder.length;
        if (n == 0) return null;

        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stk = new Stack<> ();
        stk.push(root);

        for (int i = 1; i < n; i ++) {
            if (stk.peek().val != inorder[inPos]) {
                TreeNode cur = new TreeNode(preorder[i]);
                stk.peek().left = cur;
                stk.push(cur);
            } else {
                // 找到中间结点
                TreeNode cur = null;
                while (!stk.isEmpty() && stk.peek().val == inorder[inPos]) {
                    cur = stk.pop();
                    inPos ++;
                }
                cur.right = new TreeNode(preorder[i]);
                stk.push(cur.right);
            }
        }

        return root;
    }
}
